Los AG constan de tres operadores básicos: cruza, mutación y selección.¹ Los cuales son aplicados a una población de individuos, donde cada uno de ellos representa una posible solución.

1  Pseudocódigo de un AG[]

Generar una población inicial.

Evaluar la función de aptitud de cada individuo.

Determinar el porcentaje de aptitud de la población.

1. Seleccionar individuos a reproducir.
2. Aparear individuos aleatoriamente.
3. Aplicar operador de cruza.
4. Aplicar operador de mutación.
5. Evaluar aptitud de cada individuo.
6. Determinar porcentaje de la función de aptitud de la población.
7. Hasta que se cumpla la condición de término.

Problema:

Maximizar la función f(x) = x² tal que 0 £ x £ 31 usando AG's

Codificación de las variables como una cadena de tamaño finito:

Sea dicha cadena un entero binario sin signo de longitud 5 -secuencia de 0's y 1's-.

Entonces podremos representar valores decimales en el rango 0-31.

Para calcular la función de aptitud o función objetivo simplemente decodificamos el individuo y lo elevamos al cuadrado -x²-.

i) Generar la población inicial

ea la población mostrada en la siguiente tabla una población generada aleatoriamente.

ii) Evaluar la función de aptitud de cada individuo.

iii) Determinar porcentaje de aptitud de la población.

c]lllIndividuo	Aptitud -x2-	%
01101	169
11000	676
01000	64
10011	361
00011	9
11100	784

Generación 1

G1.1) Seleccionar individuos a reproducir

La selección se puede realizar usando una ruleta ''cargada'', con ello se logra que en la siguiente generación -probabilísticamente- solo permanezcan los individuos con mayor función de aptitud -mas cercanos a la función objetivo.

Nueva generación

c]lllIndividuo	Aptitud -x2-	%
01101	169
11000	676
11000	676
10011	361
00011	9
10011	361

G1.2) Aparear individuos aleatoriamente

Sean por ejemplo:

11000 y

10011

dos individuos seleccionados en forma aleatoria.

G1.3) Aplicar operador de cruza

Seleccionar aleatoriamente un sitio de cruza

c]llAntes	Después
11¢000	11¢011
10¢011	10¢000

G1.4) Aplicar operador de mutación

Supóngase que la mutación tiene una probabilidad alta -P(m) = 1-, esto significa que depués de la cruza los nuevos individuos mutarán una posición seleccionada aleatoriamente.

c]llAntes	Después
1101¢1	11010
1¢0000	11000

G1.5) Evaluar función de aptitud de los nuevos individuos

Si tal función es mejor que sus progenitores, entonces agregarlos a la población -eliminando a los padres-

Dado que 11010 es mejor que sus predecesores, es insertado en la población sustituyendo a 10011.

Nueva población

G1.6) Determinar porcentaje de la función de aptitud de la población.

c]lllIndividuo	Aptitud -x2-	%
01101	169
11010	676
11000	576
10011	361
00011	9
10011	361

Generación 2

G2.1) Seleccionar individuos a reproducir

Nueva generación

c]lllIndividuo	Aptitud -x2-	%
01101	169
11000	676
11000	676
10011	361
00011	9
10011	361

G2.2) Aparear individuos aleatoriamente

Sean por ejemplo:

11010 y

10011

G2.3) Aplicar operador de cruza

Seleccionar aleatoriamente un sitio de cruza

c]llAntes	Después
110¢10	110¢11
100¢11	100¢10

G2.4) Aplicar operador de mutación

c]llAntes	Después
11¢011	11111
1¢0010	11010

G2.5) Evaluar función de aptitud de los nuevos individuos

Dado que la funcióm de aptitud de 11111 es el máximo que estamos buscando, se cumple la condición de paro y el algoritmo termina.

References

[]

http://www.irdg.com/mep/nni/genealgo.txt

[]

Genetic Algotrithms ...

Footnotes: